package com.study.javaBasic.collections;

import java.util.*;

public class StackDemo {
    public static void main(String[] args) {
        String hex = toHex(8);
        if (hex.equalsIgnoreCase("8")) {
            System.out.println("测试通过");
        } else {
            System.out.println("测试失败");
        }
        String exp = "1 + 2 * (9 - 5)";
        SuffixExpression se = compile(exp);
        int result = Integer.parseInt(se.execute());
        System.out.println(exp + " = " + result + " " + (result==(1 + 2 * (9 - 5)) ? "✓" : "✗"));
    }

    /**
     * 转换为十六进制
     * @param n 转换前
     * @return 转换后字符串
     */
    static String toHex(int n) {
        Stack<Character> result=new Stack<>();
        StringBuilder hex=new StringBuilder();
        while(n%16>=0&&n!=0){
            if(n%16>9){
                result.push((char)(55+(n%16)));
            }else {
                result.push((char)(48+(n%16)));
            }
            n/=16;
        }
        while (!result.empty()){
            hex.append(result.pop());
        }
        System.out.println(hex.toString());
        return hex.toString();
    }

    /**
     * 中缀表达式编译为后缀表达式
     * @param infix
     * @return
     */
    static SuffixExpression compile(String infix) {
        infix=infix.replace(" ","");
        SuffixExpression suffixExpression=new SuffixExpression();
        List<String> suffix = new LinkedList<>();
        Stack<Character> stack = new Stack<>();

        // 用于记录字符长度  例如100*2,则记录的len为3 到时候截取字符串的前三位就是数字
        int len = 0;
        for(int i = 0; i < infix.length(); i++){
            char ch = infix.charAt(i);

            // 数字
            if (Character.isDigit(ch) || ch == '.') {
                len++;
                } else if (SuffixExpression.OPERATOR.indexOf(ch) != -1) {
                    // 符号之前的可以截取下来做数字
                    if (len > 0) {
                        suffix.add(infix.substring(i-len, i));
                    len = 0;
                }
                // 将左括号放入栈中
                if (ch == '(') {
                    stack.push(ch);
                    continue;
                }
                if (!stack.isEmpty()) {
                    int size = stack.size() - 1;
                    boolean flag = false;

                    // 若当前ch为右括号，则栈里元素从栈顶一直弹出，直到弹出到左括号
                    while(size >= 0 && ch == ')' && stack.peek() != '('){
                        suffix.add(String.valueOf(stack.pop()));
                        size--;
                        flag = true;
                    }

                    // 若取得不是（）内的元素，并且当前栈顶元素的优先级>=对比元素 那就出栈插入队列
                    while(size >= 0 && !flag && SuffixExpression.PRIORITY_MAP.get(stack.peek()) >= SuffixExpression.PRIORITY_MAP.get(ch)){
                        suffix.add(String.valueOf(stack.pop()));
                        size--;
                    }
                }

                if (ch != ')') {
                    stack.push(ch);
                }else {
                    stack.pop();
                }
            }
            // 如果已经走到了中缀表达式的最后一位
            if (i == infix.length() - 1) {
                if (len > 0) {
                    suffix.add(infix.substring(i - len + 1, i + 1));
                }

                int size = stack.size() - 1;
                // 一直将栈内 符号全部出栈并且加入队列中
                while(size >= 0) {
                    suffix.add(String.valueOf(stack.pop()));
                    size--;
                }
            }
        }
        suffixExpression.suffix=suffix.toString().substring(1, suffix.toString().length()-1);
        return suffixExpression;

    }
}

class SuffixExpression {
    public static final Map<Character,Integer> PRIORITY_MAP = new HashMap<>();
    public static final String OPERATOR = "*/+-()";

    static{
        PRIORITY_MAP.put('-', 1);
        PRIORITY_MAP.put('+', 1);
        PRIORITY_MAP.put('*', 2);
        PRIORITY_MAP.put('/', 2);
        PRIORITY_MAP.put('(', 0);
    }

    public String suffix="";
    String execute() {
        String [] arr = suffix.split(",");
        Stack<String> stack = new Stack<>();

        for (int i = 0; i < arr.length; i++) {
            switch (arr[i].trim()) {
                case "+":
                    double a = Double.parseDouble(stack.pop()) + Double.parseDouble(stack.pop());
                    stack.push(String.valueOf(a));
                    break;
                case "-":
                    double b = Double.parseDouble(stack.pop()) - Double.parseDouble(stack.pop());
                    stack.push(String.valueOf(-b));
                    break;
                case "*":
                    double c = Double.parseDouble(stack.pop()) * Double.parseDouble(stack.pop());
                    stack.push(String.valueOf(c));
                    break;
                case "/":
                    double d = Double.parseDouble(stack.pop()) / Double.parseDouble(stack.pop());
                    stack.push(String.valueOf(d));
                    break;
                default:
                    stack.push(arr[i].trim());
                    break;
            }
        }

        return stack.size() == 1 ? stack.pop() : "运算失败" ;
    }
}